<?php
$arr = [1, 10, 6, 5, 7, 3, 4, 9, 8, 2];

function maoPaoSort($arr)
{
    $length = count($arr);
    if ($length <= 0) {
        return false;
    }
    for ($i = 0; $i < $length - 1; $i++) {
        for ($j = 0; $j < $length - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $tem = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $tem;
            }
        }
    }
    return $arr;
}

function changeSort($arr)
{
    $length = count($arr);
    if ($length <= 0) {
        return false;
    }
    for ($i = 0; $i < $length - 1; $i++) {
        $maxKey = $i;
        for ($j = $i; $j < $length; $j++) {
            if ($arr[$maxKey] > $arr[$j]) {
                $maxKey = $j;
            }
        }
        if ($maxKey != $i) {
            $tem = $arr[$i];
            $arr[$i] = $arr[$maxKey];
            $arr[$maxKey] = $tem;
        }
    }
    return $arr;
}

function insertSort($arr)
{
    $length = count($arr);
    if ($length <= 0) {
        return false;
    }
    for ($i = 0; $i < $length; $i++) {
        $key = $i - 1;
        $value = $arr[$i];
        while ($key > 0 && $arr[$key] > $value) {
            $arr[$key + 1] = $arr[$key];
            $key--;
        }
        $arr[$key + 1] = $value;
    }
    return $arr;
}

function quickSort($arr)
{
    $length = count($arr);
    if ($length <= 1) {
        return $arr;
    }
    $left = $right = [];
    for ($i = 1; $i < $length; $i++) {
        if ($arr[$i] > $arr[0]) {
            $right[] = $arr[$i];
        } else {
            $left[] = $arr[$i];
        }
    }
    $leftArr = quickSort($left);
    $rightArr = quickSort($right);
    return array_merge($leftArr, [$arr[0]], $rightArr);
}

function halfFind($x, $arr)
{
    $length = count($arr);
    if ($length <= 0) {
        return false;
    }
    $minKey = 0;
    $maxKey = $length - 1;
    while ($minKey <= $maxKey) {
        $middleKey = intval(($maxKey + $minKey) / 2);
        if ($arr[$middleKey] > $x) {
            $maxKey = $middleKey - 1;
        } elseif ($arr[$middleKey] < $x) {
            $minKey = $middleKey + 1;
        } else {
            return $middleKey;
        }
    }
    return false;
}

$sortArr = quickSort($arr);
